1. Field of the Invention
The present invention is relates generally to the field of high-speed digital data processing systems, and more particularly to systems and methods of routing packets in multiprocessor computer systems.
2. Background Information
High-end multiprocessor computer systems typically consist of nodes interconnected by physical communication links. Often the physical links connect the nodes in a multi-dimensional topology. Router logic connected to the physical links routes packets through the interconnect network to their destination nodes as a function of a destination code or address associated with each destination node. The appropriate route is typically selected using a routing table located on each processor node.
Routing tables can, however, get prohibitively expensive as the number of nodes in the system increase. A routing table architecture that reduces the number of entries needed is detailed by Galles et al. in “Programmable, Distributed Network Routing,” in U.S. Pat. No. 5,721,819, issued Feb. 24, 1998. An alternate routing table architecture is detailed by Passint et al. in “Router Table Lookup Mechanism,” in U.S. Pat. No. 5,970,232, issued Oct. 19, 1999. Both approaches use a local/remote approach in which a local table is used to route to nodes close to the node forwarding the packet and a remote table is used to route packets in a direction that is generally in the direction of the destination node. Since routing to the remote node is done in a general manner, fewer entries are needed to handle all the possible destination codes.
Such approaches are effective in reducing the number of entries needed to implement a routing table in each node, but at the cost of reduced routing flexibility. What is needed is an efficient yet flexible system and method for implementing programmable routing tables in multiprocessor systems.